Sequence container (C++)

In computing, sequence containers refer to a group of container class templates in the standard library of the C++ programming language that implement storage of data elements. Being templates, they can be used to store arbitrary elements, such as integers or custom classes. One common property of all sequential containers is that the elements can be accessed sequentially. Like all other standard library components, they reside in namespace std.

The following containers are defined in the current revision of the C++ standard: array, vector, list, forward_list, deque. Each of these containers implement a different algorithms for data storage, which means that they have different speed guarantees for different operations:^[1]

• array implements a compile-time non-resizeable array.
• vector implements an array with fast random access and an ability to automatically resize when appending elements.
• deque implements a double-ended queue with comparatively fast random access.
• list implements a doubly linked list.
• forward_list implements a singly linked list.

Since each of the containers needs to be able to copy its elements in order to function properly, the type of the elements must fulfill CopyConstructible and Assignable requirements.^[2] For a given container all elements must belong to the same type. For instance, one cannot store data in the form of both char and int within the same container instance.

History

Originally, only vector, list, deque were defined. Until the standardization of the C++ language in 1998, they were part of the Standard Template Library, published by SGI.

The array container at first appeared in several books under various names. Later it was incorporated into boost C++ libraries and was proposed into the standard C++ library. The motivation for inclusion of array was that it solves two problems of the C-style array: the lack of STL-like interface and inability to be copied as any other object. It firstly appeared in C++ TR1 and later was incorporated into C++11.

The forward_list container has been added to C++11 as a space-efficient alternative to list when reverse iteration is not needed.

Properties

array, vector and deque all support fast random access to the elements. list supports only bidirectional iteration, whereas forward_list supports only unidirectional iteration.

array does not support element insertion or removal. vector supports fast element insertion or removal at the end. Any insertion or removal of an element not at the end of the vector needs elements between the insertion position and the end of the vector to be copied. The iterators to the affected elements are thus invalidated. Also, if the allocated storage in the vector is too small to insert elements, a new array is allocated, all elements are copied or moved to the new array, and the old array is freed. deque, list and forward_list all support fast insertion or removal of elements anywhere in the container. list and forward_list preserves validity of iterators on such operation, whereas deque invalidates all of them.

Vector

The elements of a vector are stored contiguously.^[3] Like all dynamic array implementations, vectors have low memory usage and good locality of reference and data cache utilization. Unlike other STL containers, such as deques and lists, vectors allow the user to denote an initial capacity for the container.

Vectors allow random access; that is, an element of a vector may be referenced in the same manner as elements of arrays (by array indices). Linked-lists and sets, on the other hand, do not support random access or pointer arithmetic.

The vector data structure is able to quickly and easily allocate the necessary memory needed for specific data storage. This is particularly useful for storing data in lists whose length may not be known prior to setting up the list but where removal (other than, perhaps, at the end) is rare. Erasing elements from a vector or even clearing the vector entirely does not necessarily free any of the memory associated with that element.

Vectors are inefficient at removing or inserting elements other than at the end. Such operations have O(n) (see Big-O notation) complexity compared with O(1) for linked-lists. This is offset by the speed of access — access to a random element in a vector is of complexity O(1) compared with O(n) for general linked-lists and O(log n) for link-trees.

Capacity and reallocation

A typical vector implementation consists, internally, of a pointer to a dynamically allocated array,^[1] and possibly data members holding the capacity and size of the vector. The size of the vector refers to the actual number of elements, while the capacity refers to the size of the internal array.

When new elements are inserted, if the new size of the vector becomes larger than its capacity, reallocation occurs.^[1][4] This typically causes the vector to allocate a new region of storage, move the previously held elements to the new region of storage, and free the old region.

Because the addresses of the elements change during this process, any references or iterators to elements in the vector become invalidated.^[5] Using an invalidated reference causes undefined behaviour.

The reserve() operation may be used to prevent unnecessary reallocations. After a call to reserve(n), the vector's capacity is guaranteed to be at least n.^[6]

The vector maintains a certain order of its elements, so that when a new element is inserted at the beginning or in the middle of the vector, subsequent elements are moved backwards in terms of their assignment operator or copy constructor. Consequently, references and iterators to elements after the insertion point become invalidated.^[7]

C++ vectors do not support in-place reallocation of memory, by design; i.e., upon reallocation of a vector, the memory it held will always be copied to a new block of memory using its elements' copy constructor, and then released. This is inefficient for cases where the vector holds plain old data and additional contiguous space beyond the held block of memory is available for allocation.

Specialization for bool

The Standard Library defines a specialization of the vector template for bool. The description of this specialization indicates that the implementation should pack the elements so that every bool only uses one bit of memory.^[8] This is widely considered a mistake.^[9][10] vector<bool> does not meet the requirements for a C++ Standard Library container. For instance, a container<T>::reference must be a true lvalue of type T. This is not the case with vector<bool>::reference, which is a proxy class convertible to bool.^[11] Similarly, the vector<bool>::iterator does not yield a bool& when dereferenced. There is a general consensus among the C++ Standard Committee and the Library Working Group that vector<bool> should be deprecated and subsequently removed from the standard library, while the functionality will be reintroduced under a different name.^[12]

List

The list data structure implements a doubly linked list. Data is stored non-contiguously in memory which allows the list data structure to avoid the reallocation of memory that can be necessary with vectors when new elements are inserted into the list.

The list data structure allocates and deallocates memory as needed; therefore, it does not allocate memory that it is not currently using. Memory is freed when an element is removed from the list.

Lists are efficient when inserting new elements in the list; this is an O(1) operation. No shifting is required like with vectors.

Lists do not have random access ability like vectors (O(1) operation). Accessing a node in a list is an O(n) operation that requires a list traversal to find the node that needs to be accessed.

With small data types (such as ints) the memory overhead is much more significant than that of a vector. Each node takes up sizeof(type) + 2 * sizeof(type*). Pointers are typically one word (usually four bytes), which means that a list of four byte integers takes up approximately three times as much memory as a vector of integers.

Deque

deque is a container class template that implements a double-ended queue. It provides similar computational complexity to vector for most operations, with the notable exception that it provides amortized constant-time insertion and removal from both ends of the element sequence. Unlike vector, deque uses discontiguous blocks of memory, and provides no means to control the capacity of the container and the moment of reallocation of memory. Like vector, deque offers support for random access iterators, and insertion and removal of elements invalidates all iterators to the deque.

Array

array implements a compile-time non-resizeable array. The size is determined at compile-time by a template parameter. By design, the container does not support allocators. Unlike the other standard containers, array does not provide constant-time swap.

Overview of functions

The containers are defined in headers named after the names of the containers, e.g. vector is defined in header <vector>. All containers satisfy the requirements of the Container concept, which means they have begin(), end(), size(), max_size(), empty(), and swap() methods.

There are other operations that are available as a part of the list class and there are algorithms that are part of the C++ STL (Algorithm (C++)) that can be used with the list class.

• Operations
  • list::merge - Merges two sorted lists
  • list::splice - Moves elements from another list
  • list::remove - Removes elements equal to the given value
  • list::remove_if - Removes elements satisfying specific criteria
  • list::reverse - Reverses the order of the elements
  • list::unique - Removes consecutive duplicate elements
  • list::sort - Sorts the element

• Modifiers
  • array::fill - Fills the array with the given value

Usage example

The following example demonstrates various techniques involving a vector and C++ Standard Library algorithms, notably shuffling, sorting, finding the largest element, and erasing from a vector using the erase-remove idiom.

#include <iostream>
#include <vector>
#include <algorithm> // sort, max_element, random_shuffle, remove_if, lower_bound 
#include <functional> // greater, bind2nd
// used here for convenience, use judiciously in real programs. 
using namespace std;
 
int main()
{
  int arr[4] = {1, 2, 3, 4};
  // initialize a vector from an array
  vector<int> numbers(arr, arr+4);
  // insert more numbers into the vector
  numbers.push_back(5);
  numbers.push_back(6);
  numbers.push_back(7);
  numbers.push_back(8);
  // the vector currently holds {1, 2, 3, 4, 5, 6, 7, 8}
 
  // randomly shuffle the elements
  random_shuffle( numbers.begin(), numbers.end() );
 
  // locate the largest element, O(n)
  vector<int>::const_iterator largest = 
    max_element( numbers.begin(), numbers.end() );
 
  cout << "The largest number is " << *largest << "\n";
  cout << "It is located at index " << largest - numbers.begin() << "\n";
 
  // sort the elements
  sort( numbers.begin(), numbers.end() );
 
  // find the position of the number 5 in the vector, O(log n)  
  vector<int>::const_iterator five = 
    lower_bound( numbers.begin(), numbers.end(), 5 );  
 
  cout << "The number 5 is located at index " << five - numbers.begin() << "\n";
 
  // erase all the elements greater than 4   
  numbers.erase( remove_if(numbers.begin(), numbers.end(), 
    bind2nd(greater<int>(), 4) ), numbers.end() );
 
  // print all the remaining numbers
  for(vector<int>::const_iterator it = numbers.begin(); it != numbers.end(); ++it)
  {
    cout << *it << " ";
  }
 
  return 0;
}

The output will be the following:

The largest number is 8
It is located at index 6 (implementation-dependent)
The number 5 is located at index 4
1 2 3 4

Example of 2 dimensional dynamic vector array, and accessing and modifying it:

typedef std::vector< std::vector<int> > pxMP;
 
void function()
{
    int sizeX, sizeY; // size can be set on-the-fly.
    pxMP pxMap(sizeX, std::vector<int>(sizeY)); // X/Y array of pixels 0,1.
    pxMap[0][5] = 1;  /* accessing it */
 
        // delete left and right columns:
        pxMap.pop_back();
        pxMap.erase(pxMap.begin());
 
        // delete top and bottom rows of all columns, first make some tools:
        std::vector< std::vector<int> >::iterator iterlvl2; // iterator level 2 dimension.
        std::vector< int >::iterator iterlvl1; // iterator level 1 dimension
 
        // lets' go deeper. We must go deeper.
        for (iterlvl2=pxMap.begin();iterlvl2 != pxMap.end();iterlvl2++)
        {
            iterlvl1 = (*iterlvl2).begin(); // demo purpose only.
            (*iterlvl2).pop_back();
            (*iterlvl2).erase((*iterlvl2).begin()); // where are we?
 
            sizeY = (*iterlvl2).size(); // set new sizeY while on this level, once we return to the higher level we cannot retrieve... 
        }
        /* that was cool */
}

Example of 1 dimensional dynamic vector array, and sorting and removing all duplicate entries:

#include <vector>
#include <string>
#include <algorithm> // for generic algorithms: sort / unique / erase
 
void main() {
 
    vector<string> v_str;    // empty vector v_str
    v_str.push_back("zz");   // {"zz"}
    v_str.push_back("aa");   // {"zz", "aa")
    v_str.push_back("bb");   // {"zz", "aa", "bb")
    v_str.push_back("aa");   // {"zz", "aa", "bb", "aa")
    v_str.push_back("xx");   // {"zz", "aa", "bb", "aa", "xx")
    v_str.push_back("dd");   // {"zz", "aa", "bb", "aa", "xx", "dd")
    v_str.push_back("xx");   // {"zz", "aa", "bb", "aa", "xx", "dd", "xx")
 
    // sort all the elements of the vector
    sort(v_str.begin(), v_str.end());    
    // the result is the sorting of the elements: {"aa", "aa", "bb", "dd", "xx", "xx", "zz"}
 
    // remove duplicate entries
    v_str.erase( unique(v_str.begin(), v_str.end() ), v_str.end() );   
    // the result is sorted and unique elements: {"aa","bb","dd","xx","zz"}
 
    return void;
}

The following example demonstrates various techniques involving a list and C++ Standard Library algorithms, notably shuffling, sorting, finding the largest element, and erasing from a list using the erase-remove idiom. Example is based on the example used in the Vector (C++) entry to maintain consistency for comparative analysis.

#include <iostream>
#include <list>
#include <algorithm> // max_element, random_shuffle, remove_if, lower_bound 
#include <functional> // greater, bind2nd
#include <iterator>   // distance function
 
// unary function that doubles the value of its argument.
int multby2(int& x) 
{
    x *= 2;
    return x;
}
 
int main()
{
    // initialize a list  of integers
    std::list<int> numbers;
 
    // insert numbers onto the front of the list
    numbers.push_front(4);
    numbers.push_front(3);
    numbers.push_front(2);
    numbers.push_front(1);
    // the list currently holds (1, 2, 3, 4)
 
    // insert numbers to the back of the list
    numbers.push_back(5);
    numbers.push_back(6);
    numbers.push_back(7);
    numbers.push_back(8);
    // the list currently holds (1, 2, 3, 4, 5, 6, 7, 8)
 
    // reverse the elements of a list
    numbers.reverse();
 
    // print all the remaining numbers (uses C++11 range for loop syntax)
    for (auto number : numbers) {
        std::cout << *it << " ";
    }
    std::cout << '\n';
 
    // locate the largest element, O(n)
    std::list<int>::const_iterator largest = std::max_element(numbers.begin(), numbers.end());
 
    std::cout << "The largest number is " << *largest << "\n";
 
    // sort the elements
    numbers.sort();
 
    // find the position of the number 5 in the list, O(log n) , 
    // and performs a binary search (assumes list is ordered) to find where 5 could be inserted
    // binary_search is used in the same way, but returns a bool value
    std::list<int>::iterator five = std::lower_bound(numbers.begin(), numbers.end(), 5);  
 
    // distance function is O(n), and this is because list do not have random access iterators. 
    std::cout << "5 is found at node: " << std::distance(numbers.begin(), five) + 1 << '\n';
 
    // find the position of the number 5 in the list, O(n), but does not depend on the list being sorted
    std::list<int>::iterator fiveagain = std::find(numbers.begin(), numbers.end(), 5);
 
    std::cout << "5 is found at node: " << std::distance(numbers.begin(), five) + 1 << '\n';
 
 
    // erase all the elements greater than 4   
    numbers.erase(std::remove_if(numbers.begin(), numbers.end(), 
                             std::bind2nd(std::greater<int>(), 4)), numbers.end());
 
    // multiply each number by 2
    std::for_each(numbers.begin(), numbers.end(), multby2);
 
    // print all the remaining numbers (uses C++11 range for loop)
    for (auto number : numbers) {
        std::cout << number << " ";
    }
 
    return 0;
}

The output will be the following:

"1 2 3 4 5 6 7 8"
"The largest number is 8"
"5 is found at node: 5"
"5 is found at node: 5"
"2 4 6 8"

Example:

#include <vector>
int main()
{
  std::vector<int> v(2); // constructs a vector holding two ints
 
  // make references to the two ints
  int& first = v.front(); 
  int& last = v.back();
 
  v.insert(v.begin() + 1, 1, 1); // insert a new int in the middle of the vector. 
 
  int i = first; // undefined behaviour if the previous insert caused reallocation
  int j = last; // undefined behaviour per the C++ standard, §23.2.4.3/1
}

References

• William Ford, William Topp. Data Structures with C++ and STL, Second Edition. Prentice Hall, 2002. ISBN 0-13-085850-1. Chapter 4: The Vector Class, pp.195–203.
• Josuttis, Nicolai M. (1999). The C++ Standard Library. Addison-Wesley. ISBN 0-201-37926-0. 

Notes